home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / gawk / gawk213s.zoo / gawk-src-2.13 / dfa.c < prev    next >
C/C++ Source or Header  |  1991-05-10  |  62KB  |  2,310 lines
  1. /* dfa.c - determinisitic extended regexp routines for GNU
  2.    Copyright (C) 1988 Free Software Foundation, Inc.
  3.                       Written June, 1988 by Mike Haertel
  4.               Modified July, 1988 by Arthur David Olson
  5.              to assist BMG speedups
  6.  
  7.                NO WARRANTY
  8.  
  9.   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  10. NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  11. WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  12. RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  13. WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  14. BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  15. FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  16. AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  17. DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  18. CORRECTION.
  19.  
  20.  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  21. STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  22. WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  23. LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  24. OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  25. USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  26. DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  27. A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  28. PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  29. DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  30.  
  31.         GENERAL PUBLIC LICENSE TO COPY
  32.  
  33.   1. You may copy and distribute verbatim copies of this source file
  34. as you receive it, in any medium, provided that you conspicuously and
  35. appropriately publish on each copy a valid copyright notice "Copyright
  36.  (C) 1988 Free Software Foundation, Inc."; and include following the
  37. copyright notice a verbatim copy of the above disclaimer of warranty
  38. and of this License.  You may charge a distribution fee for the
  39. physical act of transferring a copy.
  40.  
  41.   2. You may modify your copy or copies of this source file or
  42. any portion of it, and copy and distribute such modifications under
  43. the terms of Paragraph 1 above, provided that you also do the following:
  44.  
  45.     a) cause the modified files to carry prominent notices stating
  46.     that you changed the files and the date of any change; and
  47.  
  48.     b) cause the whole of any work that you distribute or publish,
  49.     that in whole or in part contains or is a derivative of this
  50.     program or any part thereof, to be licensed at no charge to all
  51.     third parties on terms identical to those contained in this
  52.     License Agreement (except that you may choose to grant more extensive
  53.     warranty protection to some or all third parties, at your option).
  54.  
  55.     c) You may charge a distribution fee for the physical act of
  56.     transferring a copy, and you may at your option offer warranty
  57.     protection in exchange for a fee.
  58.  
  59. Mere aggregation of another unrelated program with this program (or its
  60. derivative) on a volume of a storage or distribution medium does not bring
  61. the other program under the scope of these terms.
  62.  
  63.   3. You may copy and distribute this program or any portion of it in
  64. compiled, executable or object code form under the terms of Paragraphs
  65. 1 and 2 above provided that you do the following:
  66.  
  67.     a) accompany it with the complete corresponding machine-readable
  68.     source code, which must be distributed under the terms of
  69.     Paragraphs 1 and 2 above; or,
  70.  
  71.     b) accompany it with a written offer, valid for at least three
  72.     years, to give any third party free (except for a nominal
  73.     shipping charge) a complete machine-readable copy of the
  74.     corresponding source code, to be distributed under the terms of
  75.     Paragraphs 1 and 2 above; or,
  76.  
  77.     c) accompany it with the information you received as to where the
  78.     corresponding source code may be obtained.  (This alternative is
  79.     allowed only for noncommercial distribution and only if you
  80.     received the program in object code or executable form alone.)
  81.  
  82. For an executable file, complete source code means all the source code for
  83. all modules it contains; but, as a special exception, it need not include
  84. source code for modules which are standard libraries that accompany the
  85. operating system on which the executable file runs.
  86.  
  87.   4. You may not copy, sublicense, distribute or transfer this program
  88. except as expressly provided under this License Agreement.  Any attempt
  89. otherwise to copy, sublicense, distribute or transfer this program is void and
  90. your rights to use the program under this License agreement shall be
  91. automatically terminated.  However, parties who have received computer
  92. software programs from you with this License Agreement will not have
  93. their licenses terminated so long as such parties remain in full compliance.
  94.  
  95.   5. If you wish to incorporate parts of this program into other free
  96. programs whose distribution conditions are different, write to the Free
  97. Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  98. worked out a simple rule that can be stated here, but we will often permit
  99. this.  We will be guided by the two goals of preserving the free status of
  100. all derivatives our free software and of promoting the sharing and reuse of
  101. software.
  102.  
  103.  
  104. In other words, you are welcome to use, share and improve this program.
  105. You are forbidden to forbid anyone else to use, share and improve
  106. what you give them.   Help stamp out software-hoarding!  */
  107.  
  108. #include "awk.h"
  109. #include <assert.h>
  110.  
  111. #ifdef setbit  /* surprise - setbit and clrbit are macros on NeXT */
  112. #undef setbit
  113. #endif
  114. #ifdef clrbit
  115. #undef clrbit
  116. #endif
  117.  
  118. #ifdef __STDC__
  119. typedef void *ptr_t;
  120. #else
  121. typedef char *ptr_t;
  122. #endif
  123.  
  124. typedef struct {
  125.     char **    in;
  126.     char *    left;
  127.     char *    right;
  128.     char *    is;
  129. } must;
  130.  
  131. static ptr_t xcalloc P((int n, size_t s));
  132. static ptr_t xmalloc P((size_t n));
  133. static ptr_t xrealloc P((ptr_t p, size_t n));
  134. static int tstbit P((int b, _charset c));
  135. static void setbit P((int b, _charset c));
  136. static void clrbit P((int b, _charset c));
  137. static void copyset P((const _charset src, _charset dst));
  138. static void zeroset P((_charset s));
  139. static void notset P((_charset s));
  140. static int equal P((const _charset s1, const _charset s2));
  141. static int charset_index P((const _charset s));
  142. static _token lex P((void));
  143. static void addtok P((_token t));
  144. static void atom P((void));
  145. static void closure P((void));
  146. static void branch P((void));
  147. static void regexp P((void));
  148. static void copy P((const _position_set *src, _position_set *dst));
  149. static void insert P((_position p, _position_set *s));
  150. static void merge P((_position_set *s1, _position_set *s2, _position_set *m));
  151. static void delete P((_position p, _position_set *s));
  152. static int state_index P((struct regexp *r, _position_set *s,
  153.               int newline, int letter));
  154. static void epsclosure P((_position_set *s, struct regexp *r));
  155. static void build_state P((int s, struct regexp *r));
  156. static void build_state_zero P((struct regexp *r));
  157. static char *icatalloc P((char *old, const char *new));
  158. static char *icpyalloc P((const char *string));
  159. static char *istrstr P((char *lookin, char *lookfor));
  160. static void ifree P((char *cp));
  161. static void freelist P((char **cpp));
  162. static char **enlist P((char **cpp, char *new, size_t len));
  163. static char **comsubs P((char *left, char *right));
  164. static char **addlists P((char **old, char **new));
  165. static char **inboth P((char **left, char **right));
  166. static void resetmust P((must *mp));
  167. static void regmust P((struct regexp *r));
  168.  
  169. #undef P
  170.  
  171. static ptr_t
  172. xcalloc(n, s)
  173.      int n;
  174.      size_t s;
  175. {
  176.   ptr_t r = calloc(n, s);
  177.  
  178.   if (NULL == r)
  179.     regerror("Memory exhausted");  /* regerror does not return */
  180.   return r;
  181. }
  182.  
  183. static ptr_t
  184. xmalloc(n)
  185.      size_t n;
  186. {
  187.   ptr_t r = malloc(n);
  188.  
  189.   assert(n != 0);
  190.   if (NULL == r)
  191.     regerror("Memory exhausted");
  192.   return r;
  193. }
  194.  
  195. static ptr_t
  196. xrealloc(p, n)
  197.      ptr_t p;
  198.      size_t n;
  199. {
  200.   ptr_t r = realloc(p, n);
  201.  
  202.   assert(n != 0);
  203.   if (NULL == r)
  204.     regerror("Memory exhausted");
  205.   return r;
  206. }
  207.  
  208. #define CALLOC(p, t, n) ((p) = (t *) xcalloc((n), sizeof (t)))
  209. #undef MALLOC
  210. #define MALLOC(p, t, n) ((p) = (t *) xm